package algorithm_primary.studyMySelf.查找;

import java.util.Arrays;

/**
 * @author 衡孟浩
 * @date 2023/5/21 17:58
 */
public class 二分查找 {


    /**
     * 给定一个有序数组 和一个目标数值  判断是否有这个数值
     *
     * @param args
     */
    public static void main(String[] args) {


        int tem = 1000;
        int arrLen = 10;

        int maxValue = 10;


        for (int i = 0; i < tem; i++) {
            // lenth [0,10)   value [0,10)
            int[] arr = createArr(arrLen,maxValue);
            Arrays.sort(arr);
            // [0,1)->[0,10)
           int num = (int)(Math.random()*10);
            if (binarySearch(arr,num) != logarithmicDevice(arr,num)) {
                System.out.println("出错了");
                return;
            }
        }




        int[] arr = {1,2,3,4,5,6,7,8,88,99};
        System.out.println(binarySearch(arr, 3));
    }

    private static int[] createArr(int arrLen, int maxValue) {
        int[] arr = new int[arrLen];
        if (arrLen == 0){
            return arr;
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * maxValue);
        }
        return arr;
    }

    // 二分查找  如果arr数组有num这个值返回true
    public static boolean binarySearch(int[] arr, int num) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] == num) {
                return true;
            } else if (arr[mid] > num) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }


    /**
     * 对数器
     * @param arr
     * @param num
     * @return
     */
    private static boolean logarithmicDevice(int[] arr, int num) {
        for (int i : arr) {
            if (i == num){
                return true;
            }
        }
        return false;
    }

}
